package com.example.leetcode.linkedlist.common;

import java.util.*;
import java.util.stream.Collectors;

public class LinkedListUtils {


    /**
     * 产生一个有序的链表
     *
     * @param length
     * @return
     */
    public static ListNode generateSortedLinkedList(Integer length) {

        if (length == 0) {
            return null;
        }

        ListNode head = new ListNode(1);
        ListNode curNode = head;

        for (int i = 1; i < length; i++) {
            curNode.next = new ListNode(i + 1);
            curNode = curNode.next;
        }

        return head;
    }

    /**
     * 产生一个节点数据随机的链表
     *
     * @return
     */
    public static ListNode generateLinkedListByRandom(Integer length) {
        if (length == 0) {
            return null;
        }
        ListNode head = new ListNode();
        Random random = new Random();
        head.val = random.nextInt(100);

        ListNode curNode = head;

        for (int i = 1; i < length; i++) {
            curNode.next = new ListNode(random.nextInt(100));
            curNode = curNode.next;
        }

        return head;
    }

    public static void traverseLinkedList(ListNode head) {

        if (head == null) {
            return;
        }
        ListNode curNode = head;
        System.out.println(curNode.val);

        while (curNode.next != null) {
            curNode = curNode.next;
            System.out.println(curNode.val);
        }
    }

    public static List<Integer> getLinkedListVals(ListNode head) {
        List<Integer> result = new ArrayList<>();
        if (head == null) {
            return result;
        }
        ListNode curNode = head;
        result.add(curNode.val);

        while (curNode.next != null) {
            curNode = curNode.next;
            result.add(curNode.val);
        }
        return result;
    }

    public static ListNode generateLinkedListByArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        ListNode head = new ListNode(nums[0]);
        ListNode endNode = head;
        for (int i = 1; i < nums.length; i++) {
            endNode.next = new ListNode(nums[i]);
            endNode = endNode.next;
        }
        return head;
    }

    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode head = new ListNode(-1, null);
        ListNode endNode = head;
        ListNode curNode1 = head1;
        ListNode curNode2 = head2;
        while (curNode1 != null && curNode2 != null) {
            if (curNode1.val <= curNode2.val) {
                endNode.next = curNode1;
                curNode1 = curNode1.next;
            } else {
                endNode.next = curNode2;
                curNode2 = curNode2.next;
            }
            endNode = endNode.next;
        }
        while (curNode1 != null) {
            endNode.next = curNode1;
            curNode1 = curNode1.next;
            endNode = endNode.next;
        }
        while (curNode2 != null) {
            endNode.next = curNode2;
            curNode2 = curNode2.next;
            endNode = endNode.next;
        }
        return head.next;
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode curNode = head;
        while (curNode.next != null) {
            if (curNode.val == curNode.next.val) {
                curNode.next = curNode.next.next;
            } else {
                curNode = curNode.next;
            }
        }
        return head;
    }

    /**
     * 产生一个可以带环的链表
     *
     * @param nums
     * @param pos
     * @return
     */
    public static ListNode generateLinkedListWithCycleByArray(int[] nums, int pos) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        ListNode head = new ListNode();
        ListNode curNode = head;
        ListNode tail = null;
        for (int i = 0; i < nums.length; i++) {
            curNode.next = new ListNode(nums[i]);
            if (i == pos) {
                tail = curNode;
            }
            if (i == nums.length - 1) {
                curNode.next = tail;
            }
            curNode = curNode.next;
        }
        return head.next;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        while (!Objects.equals(curA, curB)) {
            curA = curA.next;
            curB = curB.next;
            if (curA == null && curB != null) {
                curA = headB;
            }
            if (curB == null && curA != null) {
                curB = headA;
            }
        }
        return curA;
    }

    /**
     * listA 中节点数目为 m
     * listB 中节点数目为 n
     * 1 <= m, n <= 3 * 104
     * 1 <= Node.val <= 105
     * 0 <= skipA <= m
     * 0 <= skipB <= n
     * 如果 listA 和 listB 没有交点，intersectVal 为 0
     * 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
     * <p>
     * 为了让链表中的元素能够为0，本方法做了加强
     *
     * @param intersectVal
     * @param listA
     * @param listB
     * @param skipA
     * @param skipB
     * @return
     */
    public static List<ListNode> generateLinkedListWithIntersectionNode(int intersectVal, int[] listA, int[] listB, int skipA, int skipB) {
        if (listA == null || listA.length == 0 || listB == null || listB.length == 0) {
            return Collections.emptyList();
        }
        if (listA.length < skipA || listB.length < skipB) {
            return Collections.emptyList();
        }

        List<ListNode> heads = new ArrayList<>();
        ListNode headA = new ListNode();
        ListNode headB = new ListNode();
        ListNode curA = headA;
        ListNode curB = headB;

        for (int i = 0; i < skipA; i++) {
            curA.next = new ListNode(listA[i]);
            curA = curA.next;
        }
        for (int i = 0; i < skipB; i++) {
            curB.next = new ListNode(listB[i]);
            curB = curB.next;
        }

        if (skipA < listA.length && skipB < listB.length) {
            if (listA[skipA] != intersectVal || listB[skipB] != intersectVal) {
                return Collections.emptyList();
            }
            curA.next = new ListNode(listA[skipA]);
            curB.next = curA.next;
            curA = curA.next;

            for (int i = skipA + 1; i < listA.length; i++) {
                curA.next = new ListNode(listA[i]);
                curA = curA.next;
            }
        }

        heads.add(headA.next);
        heads.add(headB.next);
        return heads;
    }

    public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode myHead = new ListNode();
        myHead.next = head;
        ListNode curNode = myHead;
        while (curNode.next != null) {
            if (curNode.next.val == val) {
                curNode.next = curNode.next.next;
            } else {
                curNode = curNode.next;
            }
        }
        return myHead.next;
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode myHead = new ListNode();
        ListNode curNode = head;
        ListNode afterNode = head.next;
        while (curNode != null) {
            curNode.next = myHead.next;
            myHead.next = curNode;
            curNode = afterNode;
            if (curNode != null) {
                afterNode = curNode.next;
            }
        }
        return myHead.next;
    }

    public static boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        if (head.next == null) {
            return true;
        }
        List<Integer> list = new ArrayList<>();
        ListNode curNode = head;
        while (curNode != null) {
            list.add(curNode.val);
            curNode = curNode.next;
        }
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            if (!list.get(left).equals(list.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode curA = l1;
        ListNode curB = l2;
        ListNode result = new ListNode();
        ListNode resultTailNode = result;
        while (true) {
            int sum = 0;
            if (curA == null && curB == null) {
                return result.next;
            }
            if (curA != null) {
                sum += curA.val;
                curA = curA.next;
            }
            if (curB != null) {
                sum += curB.val;
                curB = curB.next;
            }
            if (resultTailNode.next != null) {
                sum += resultTailNode.next.val;
            }
            int high = sum / 10;
            int low = sum % 10;
            if (resultTailNode.next == null) {
                resultTailNode.next = new ListNode();
            }
            resultTailNode.next.val = low;
            resultTailNode = resultTailNode.next;
            if (high > 0) {
                resultTailNode.next = new ListNode();
                resultTailNode.next.val = high;
            }
        }
    }

    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode myHead = new ListNode();
        myHead.next = head.next;
        // 先反转前两个节点
        ListNode left = myHead.next.next;
        myHead.next.next = head;
        head.next = left;
        if (left == null || left.next == null) {
            return myHead.next;
        }
        ListNode preLeft = head;
        ListNode right = left.next;
        ListNode rightNext;
        while (true) {
            rightNext = right.next;
            preLeft.next = right;
            right.next = left;
            left.next = rightNext;
            preLeft = left;
            left = rightNext;
            if (left == null || left.next == null) {
                return myHead.next;
            }
            right = left.next;
        }
    }

    public static ListNode mergeKListsPro(ListNode[] lists) {
        ListNode myhead = new ListNode();
        ListNode tail = myhead;
        int k = lists.length;
        ListNode[] curNodes = new ListNode[k];
        System.arraycopy(lists, 0, curNodes, 0, k);

        PriorityQueue<ListNodePro> queue = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            if (curNodes[i] != null) {
                queue.add(new ListNodePro(curNodes[i].val, curNodes[i]));
            }
        }

        while (!queue.isEmpty()) {
            ListNode node = queue.poll().node;
            tail.next = node;
            if (node.next != null) {
                queue.add(new ListNodePro(node.next.val, node.next));
            }
            tail = tail.next;
        }
        return myhead.next;
    }


    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode myhead = new ListNode();
        ListNode tail = myhead;
        int k = lists.length;
        ListNode[] curNodes = new ListNode[k];
        System.arraycopy(lists, 0, curNodes, 0, k);
        int endNum = 0;
        boolean[] end = new boolean[k];

        for (int i = 0; i < k; i++) {
            if (curNodes[i] == null) {
                end[i] = true;
                endNum++;
            }
        }

        int lastMinPosStart = 0;
        int minPos = 0;

        while (endNum != k) {

            for (int i = lastMinPosStart; i < k; i++) {
                if (!end[i]) {
                    minPos = i;
                    lastMinPosStart = minPos;
                    break;
                }
            }
            ListNode minNode = curNodes[minPos];

            for (int i = minPos + 1; i < k; i++) {
                if (end[i]) {
                    continue;
                }
                if (curNodes[i] != null && curNodes[i].val < Objects.requireNonNull(minNode).val) {
                    minNode = curNodes[i];
                    minPos = i;
                }
            }
            tail.next = minNode;
            curNodes[minPos] = Objects.requireNonNull(curNodes[minPos]).next;
            if (curNodes[minPos] == null) {
                endNum++;
                end[minPos] = true;
            }
            tail = tail.next;
        }
        return myhead.next;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }
        ListNode myHead = new ListNode();
        ListNode right = findKthNodeBehindCurNode(head, k - 1);
        ListNode left = head;
        ListNode preLeft;
        if (right == null) {
            return head;
        }
        ListNode rightNext = right.next;
        // 交换前面k个节点
        myHead.next = right;
        reverseLinkedListBetweenTwoNode(left, k);
        left.next = rightNext;
        preLeft = left;
        left = rightNext;
        right = findKthNodeBehindCurNode(left, k - 1);
        if (left == null || right == null) {
            return myHead.next;
        }
        while (left != null && right != null) {
            rightNext = right.next;
            preLeft.next = right;
            reverseLinkedListBetweenTwoNode(left, k);
            left.next = rightNext;
            preLeft = left;
            left = rightNext;
            right = findKthNodeBehindCurNode(left, k - 1);
        }
        return myHead.next;
    }

    /**
     * 反转两个节点之间的指针
     */
    private static void reverseLinkedListBetweenTwoNode(ListNode left, int k) {
        ListNode first = left;
        ListNode second = left.next;
        ListNode third = left.next.next;
        // 一组k个节点,需要反转left节点之后的k-1个指针
        for (int i = 0; i < k - 1; i++) {
            second.next = first;
            first = second;
            second = third;
            if (third != null) {
                third = third.next;
            } else {
                break;
            }
        }
    }

    /**
     * 找到当前节点之后的第k个节点
     * k==0时, result = curNode;
     * k==1时, result = curNode.next;
     * <p>
     * 如果后续不足k个节点,返回null
     *
     * @param curNode
     * @param k
     * @return
     */
    private static ListNode findKthNodeBehindCurNode(ListNode curNode, int k) {
        ListNode result = curNode;
        for (int i = 0; i < k; i++) {
            if (result != null) {
                result = result.next;
            } else {
                return null;
            }
        }
        return result;
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        if (k == 0) {
            return head;
        }

        ListNode myHead = new ListNode();
        ListNode left = head;
        ListNode right = head;
        int nodeCount = 0;
        while (right != null) {
            nodeCount++;
            right = right.next;
        }
        k = k % nodeCount;
        if (k == 0) {
            return head;
        }

        right = head;
        for (int i = 0; i < k; i++) {
            right = right.next;
        }

        while (right.next != null) {
            right = right.next;
            left = left.next;
        }
        myHead.next = left.next;
        right.next = head;
        left.next = null;
        return myHead.next;
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left == right) {
            return head;
        }
        ListNode myHead = new ListNode();
        myHead.next = head;
        ListNode preLeft = myHead;
        for (int i = 0; i < left - 1; i++) {
            preLeft = preLeft.next;
        }
        ListNode leftNode = preLeft.next;
        ListNode rightNode = myHead;
        for (int i = 0; i < right; i++) {
            rightNode = rightNode.next;
        }
        ListNode rightNext = rightNode.next;
        preLeft.next = rightNode;
        reverseBetween(leftNode, right - left);
        leftNode.next = rightNext;
        return myHead.next;
    }

    private static void reverseBetween(ListNode leftNode, int k) {
        ListNode first = leftNode;
        ListNode second = leftNode.next;
        ListNode third;
        int i = 0;
        while (true) {
            third = second.next;
            second.next = first;
            i++;
            if (i == k) {
                break;
            }
            first = second;
            second = third;
        }
    }

    private static Map<Node, Node> cacheNodeMap = new HashMap<>();

    public static Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node result;
        if (cacheNodeMap.get(head) != null) {
            result = cacheNodeMap.get(head);
        } else {
            result = new Node(head.val);
            cacheNodeMap.put(head, result);
            result.next = copyRandomList(head.next);
            result.random = copyRandomList(head.random);
        }
        return result;
    }

    public static Node generateLinkedListByArray(Integer[][] nums) {
        List<Node> nodes = new ArrayList<>();
        Node myHead = new Node();
        Node tail = myHead;
        for (Integer[] num : nums) {
            Node node = new Node(num[0]);
            tail.next = node;
            nodes.add(node);
            tail = tail.next;
        }
        tail = myHead;
        for (Integer[] num : nums) {
            if (num[1] == null) {
                tail.next.random = null;
            } else {
                tail.next.random = nodes.get(num[1]);
            }
            tail = tail.next;
        }
        return myHead.next;
    }

    public static List<List<Integer>> getLinkedListVals(Node head) {
        List<List<Integer>> result = new ArrayList<>();
        if (head == null) {
            return result;
        }
        Map<Node, Integer> map = new HashMap<>();

        Node myHead = new Node();
        myHead.next = head;
        Node curNode = myHead.next;
        int index = -1;
        while (curNode != null) {
            index++;
            map.put(curNode, index);
            curNode = curNode.next;
        }
        curNode = myHead.next;
        while (curNode != null) {
            List<Integer> list = new ArrayList<>();
            list.add(curNode.val);
            list.add(map.get(curNode.random));
            result.add(list);
            curNode = curNode.next;
        }
        return result;
    }

    public static void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode myHead = new ListNode();
        myHead.next = head;
        ListNode curNode = myHead.next;
        List<ListNode> nodes = new ArrayList<>();
        while (curNode != null) {
            nodes.add(curNode);
            curNode = curNode.next;
        }
        int left = 0;
        int right = nodes.size() - 1;
        ListNode tail = myHead;
        while (left <= right) {
            tail.next = nodes.get(left);
            tail = tail.next;
            left++;
            if (left > right) {
                break;
            }
            tail.next = nodes.get(right);
            tail = tail.next;
            right--;
        }
        tail.next = null;
    }

    public static ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode curNode = head;
        while (curNode != null) {
            list.add(curNode);
            curNode = curNode.next;
        }
        return list.get(list.size() / 2);
    }

    public static ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode curNode = head;
        while (curNode != null) {
            list.add(curNode);
            curNode = curNode.next;
        }
        List<ListNode> sortedList = list.stream().sorted(Comparator.comparingInt(o -> o.val)).collect(Collectors.toList());
        ListNode myHead = new ListNode();
        curNode = myHead;
        for (ListNode node : sortedList) {
            node.next = null;
            curNode.next = node;
            curNode = curNode.next;
        }
        return myHead.next;
    }

    public static ListNode removeNodes(ListNode head) {
        ListNode newHead = reverseList(head);
        int max = 0;
        ListNode myHead = new ListNode();
        myHead.next = newHead;
        ListNode tail = myHead;
        while (tail.next != null) {
            int val = tail.next.val;
            if (max > val) {
                tail.next = tail.next.next;
            } else {
                tail = tail.next;
            }
            max = Math.max(max, val);
        }
        return reverseList(myHead.next);
    }

    public static ListNode deleteDuplicatesII(ListNode head) {
        ListNode myHead = new ListNode();
        myHead.next = head;
        ListNode curNode = head;
        ListNode preNode = myHead;
        while (curNode != null && curNode.next != null) {
            if (curNode.val != curNode.next.val) {
                curNode = curNode.next;
                preNode = preNode.next;
            } else {
                while (true) {
                    if (curNode.next == null || curNode.next.val != curNode.val) {
                        break;
                    } else {
                        curNode = curNode.next;
                    }
                }
                if (curNode.next == null) {
                    preNode.next = null;
                    break;
                }
                preNode.next = curNode.next;
                curNode = curNode.next;
            }
        }
        return myHead.next;
    }

    public static ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode preA = list1;
        for (int i = 0; i < a - 1; i++) {
            preA = preA.next;
        }
        ListNode preB = preA;
        for (int i = 0; i < b - a + 2; i++) {
            preB = preB.next;
        }
        preA.next = list2;
        while (list2.next != null) {
            list2 = list2.next;
        }
        list2.next = preB;
        return list1;

    }

    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode smallHead = new ListNode();
        ListNode smallTail = smallHead;
        ListNode bigHead = new ListNode();
        ListNode bigTail = bigHead;

        ListNode cur = head;

        while (cur != null) {
            if (cur.val < x) {
                smallTail.next = cur;
                smallTail = smallTail.next;
            } else {
                bigTail.next = cur;
                bigTail = bigTail.next;
            }
            cur = cur.next;
        }

        smallTail.next = bigHead.next;
        ListNode result = smallHead.next;
        smallHead.next = null;
        bigHead.next = null;
        bigTail.next = null;
        return result;
    }
}


